import java.util.ArrayList;
import java.util.List;

class RecentCounter {
    List<Integer> list;
    public RecentCounter() {
        list=new ArrayList<>();
    }

    public int ping(int t) {
        int start=t-3000;
        list.add(t);
        int index=0;
        while (index<list.size()){
            if(list.get(index)>=start){
                break;
            }
            index++;
        }
        return list.size()-index;
    }
}



public class project {
    public int minDistance(String word1, String word2) {
        int len1=word1.length();
        int len2=word2.length();
        int[][] dp=new int[len1+1][len2+1];
        for(int i=1;i<=len1;i++){
            dp[i][0]=i;
        }
        for(int j=1;j<=len2;j++){
            dp[0][j]=j;
        }
        for(int i=1;i<=len1;i++){
            for(int j=1;j<=len2;j++){
                char ch1=word1.charAt(i-1);
                char ch2=word2.charAt(j-1);
                if(ch1==ch2){
                    dp[i][j]=dp[i-1][j-1];
                }else{
                    dp[i][j]=Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]))+1;
                }
            }
        }
        return dp[len1][len2];
    }


















    public int getMoneyAmount(int n) {
        int[][] dp=new int[n+1][n+1];
        return dfs(dp,1,n);
    }
    public int dfs(int[][] dp,int left,int right){
        if(left>=right){
            return 0;
        }
        if(dp[left][right]!=0){
            return dp[left][right];
        }
        int ret=Integer.MAX_VALUE;
        for(int i=left;i<right;i++){
            int value=i+Math.max(dfs(dp,left,i-1),dfs(dp,i+1,right));

            ret=Math.min(ret,value);
        }
        dp[left][right]=ret;
        return ret;
    }


}
